/***
 * 向二叉树中添加任务
 * @param heap 二叉树数组
 * @param node 任务
 */
export function push(heap,node){
   let index=heap.length
    heap.push(node)
    siftUp(heap,node,index)
}


/***
 * 取出二叉树的最小堆
 * @param heap
 */
export function pop(heap){
    let first=heap[0]
    if(first){
       let last=heap.pop()
        if(first!==last){
            heap[0]=last
            siftDown(heap,last,0)
        }
       return first
    }
    return null
}

/***
 * 查看二叉树最小堆
 * @param heap
 */
export function peek(heap){
     let first=heap[0]
  return first || null
}

/***
 * 向上调和二叉树
 * @param heap
 * @param node
 * @param i
 */
function siftUp(heap,node,i){
  let index=i
  while (true){
      let parentIndex=Math.floor((index-1) / 2)
      let parent=heap[parentIndex]
      if(parent && compare(parent,node) > 0){
          heap[index]=parent
          heap[parentIndex]=node
          index=parentIndex
      }else{
          return
      }
  }
}


/***
 * 向上调和二叉树
 * @param heap
 * @param node
 * @param i
 */
function siftDown(heap,node,i){
 let index=i
 while (index < heap.length){
    let leftIndex= (index + 1) * 2 - 1
    let left=heap[leftIndex]
    let rightIndex=leftIndex+1
    let right=heap[rightIndex]
    if(left && compare(left,node) < 0){
        if(right){
            if(compare(left,right) < 0){
                heap[leftIndex]=node
                heap[index]=left
                index=leftIndex
            }else{
                heap[rightIndex]=node
                heap[index]=right
                index=rightIndex
            }
        }else{
            heap[leftIndex]=node
            heap[index]=left
            index=leftIndex
        }
    }else if(right && compare(right,node) < 0){
        heap[rightIndex]=node
        heap[index]=right
        index=rightIndex
    }else {
        return
    }
 }
}

/***
 * 对比a是不是大于b
 * @param a
 * @param b
 */
function compare(a,b){
    let diff=a.sortIndex - b.sortIndex
    return diff!==0 ? diff : a.id-b.id
}

